#ifndef PRIORITYQUEUEHASH_H
#define PRIORITYQUEUEHASH_H


/*** 
	NOTE!!!!! THIS CODE IS NOT FINISHED
	PLEASE FINISH BEFORE USING
*/



#include "lib.h"


namespace Library
{

template<class V> class PriorityQueueIterator;

/**
 * @class PriorityQueue
 * A template class
 */
template<class V> class PriorityQueue
{
	friend class PriorityQueueIterator<V>;

	public:
		PriorityQueue(int32 step=10);
		~PriorityQueue();

	bool8	insert(V newItem);
	V*		remove(V *top);

protected:
   int32 m_capacity;		/*** capacity is the number of elements allocated in memory for the array */
   int32 m_size;			/*** size is the current number of elements inserted into the array. */
   int32 m_step;			/*** if size is increased above capacity step number of empty elements will be added */
   V *m_array;
};

/**
 *    step        Numer of queue items for which memory should be
 *                preallocated, that is, the initial size of the
 *                item array the queue uses. If you insert more than
 *                n items to the queue, another n items will
 *                be allocated automatically.
*/

template<class V>
inline
PriorityQueue<V>::PriorityQueue(int32 step)
{
	m_size = 0;
	m_capacity = m_step = step;

	m_array = new V[m_size];
};


/*                  
 *  pqinsert: insert an item into the queue.
 *
 *  Parameters:
 *
 *    q           Pointer to a priority queue.
 *
 *    d           Datum to be inserted.
 *
 *  Return values:
 *
 *    1           The item has been inserted.
 *
 *    0           The item could not be appended. Either the queue i
 *                pointer provided was NULL, or the function was unable 
 *                to allocate the amount of memory needed for 
 *                the new item.
 */

template<class V>
inline bool8
PriorityQueue<V>::insert(V newItem)
{
	V *tmp;
	newsize;
	
	/* allocate more memory if necessary */
	if (m_size >= m_capacity) 
	{
		int32 newsize = m_size + m_step;

		tmp = new V[newsize];
		if (!tmp)
			return false;

		for(int32 i=0;i<m_size;i++)
			tmp[i] = m_array[i];

		m_array = tmp;
		m_capacity = newsize;
		
		delete[] tmp;
		tmp = 0;
	}

	/* insert item */
	int32 i = m_size++;
	while (i > 1 && m_array[i / 2] < newItem) 
	{
		m_array[i] = m_array[i / 2];
		i /= 2;
	}
	m_array[i] = newItem;
	
	return true;	
} 


/*
 *  pqremove: remove the highest-ranking item from the queue.
 *
 *  Parameters:
 *
 *    p           Pointer to a priority queue.
 *
 *    d           Pointer to the PQDATUM variable that will hold the 
 *                datum corresponding to the queue item removed.               
 *
 *  Return values:
 *
 *    non-NULL    An item has been removed. The variable that d points
 *                to now contains the datum associated with the item
 *                in question.
 *
 *    NULL        No item could be removed. Either the queue pointer
 *                provided was NULL, or the queue was empty. The chunk
 *                of memory that d points to has not been modified.
 */

template<class V>
inline V*
PriorityQueue<V>::remove(V *top)
{	
	V tmp;
	int i = 1, j;

	if (!m_array || m_size == 1) 
		return NULL;

	*top = m_array[1];
	tmp = m_array[--m_size];
	while (i <= m_size / 2) 
	{
		j = 2 * i;
		if (j < m_size && m_array[j] < m_array[j + 1]) 
			j++;

		if (m_array[j]) <= tmp) 
			break;

		m_array[i] = m_array[j];
		i = j;
	}
	m_array[i] = tmp;
	
	return top;	
} 

	
template<class V> 
class PriorityQueueIterator
{
	public:
		PriorityQueueIterator(PriorityQueue<V>* pQueue);
		~PriorityQueueIterator();

		V		value();

		bool8	begin();
		bool8	end();

		bool8	operator++(int);
		bool8	operator--(int);

	protected:
		PriorityQueue<V>* m_queue;
};




template<class V> 
inline
PriorityQueueIterator<V>::PriorityQueueIterator(PriorityQueue<V>* pQueue)
	:m_queue(pQueue)
{
}


};


#endif